Businesses and individuals rely upon networks (e.g., the Internet) for communications and the exchange of data. Computers coupled to these networks allow users to readily gain access to and exchange data of all types (e.g., sound, text, numerical data, video, graphics, multi-media, etc.) with other computers, databases, websites, etc. This enables users to send and receive electronic mail (e-mail) messages, browse web sites, download files, participate in live discussions in chat rooms, play games in real-time, watch streaming video, listen to music, shop and trade on-line, etc. With increased network bandwidth, video-on-demand, HDTV, IP telephony, video teleconferencing, and other types of bandwidth intensive applications will become prevalent. But in each of these applications, the underlying technology is basically the same. The data is first broken up into several smaller “packets.” The data packets are then individually routed through one or more networks via a number of interconnected network devices. The network devices, such as routers, hubs, and/or switches, direct the flow of these data packets through the network to their intended destinations.
To illustrate this process, FIG. 1 shows a simplified diagram of three computers 101-103 coupled to a network 104. Any of the three computers can transmit and/or receive data over network 104 to any of the other computers coupled to that network. In order to properly route these packets, each packet contains a destination address. The destination address specifies the proper destination for that particular packet. When a packet is received by a network device, the packet's destination address is examined by the network device. Based on the destination address, the network device knows how to properly forward that particular packet. Eventually, the packet will work its way through the network to its intended destination as it is forwarded through one or more network devices.
The manner by which a network device determines how a packet is to be forwarded is shown in FIG. 2 which depicts a generic network device. Network device 201 has a number of input ports 01-04 for accepting packets from numerous sources. The incoming packets are processed by a forwarding engine 202. Forwarding engine 202 determines the destination address embedded in the packet and uses this destination address to access information stored in memory 203. The information contained in memory 203 specifies which of the output ports 01-04 that particular packet is to be routed.
One type of memory commonly used in network devices is referred to as content-addressable memory (CAM). FIG. 3 shows a typical CAM. CAMs are typically fashioned from custom designed application specific integrated circuits (ASICs). CAMs have an advantage in that they have 100 percent utilization. This means that there is no conflict issue between two different keys. Unfortunately, CAMs are very expensive to manufacture. Furthermore, CAMs are relatively small. The biggest configuration today is around 256 k×72 bits. In addition, CAMs are relatively slow; they run approximately at 200 MHz versus fast DRAMs today run at 400 MHz. Yet another drawback to CAMs is there inherently high power consumption.
Another type of memory which can be used is random access memory (RAM). RAM memory is cheaper than CAMs. With advances made in RAM fabrication techniques, they are becoming faster and cheaper. Consequently, RAM memory is becoming an increasingly attractive alternative to CAM memory amongst network device designers. Although RAM memory is relatively inexpensive, the amount of data that needs to be stored for ready reference is quite extensive. Consequently, the associated memory costs can still be quite costly. One way to reduce the amount of data to be stored involves using a technique called, “hashing.” Hashing is a scheme which provides rapid access to data which is distinguished by a key. Each data item to be stored is associated with a key. A hash function is applied to the key, and the resulting hash value is used as an index to select one of a number of results in a hash table. If, when adding a new item, the hash table already has an entry at that indicated location, then that entry's key must be compared with the given key to see if it is the same. If the two items' keys hash to the same value, a hash “collision” has occurred, and some alternative location is used.
FIG. 4 shows an exemplary hashing scheme. Hash table 401 requires a hash function 402 that takes an input (key) and transforms it to a fixed-size hash value. Next, the hash value is used to access the hash table 401. In the example shown, an input key “A” is 32 bits wide. It is transformed via hash function 402, typically a pre-determined polynomial function. The output from the hash function 402 is a shortened 20 bits. This 20 bit hash value is used as a pointer to access hash table 401. The result in hash table 401 corresponding to that key is then output to the forwarding engine to direct the packet to its proper output port. Unfortunately, there may be instances where two inputs hash to the same key. Due to these potential hash conflicts, whereby multiple inputs generate the same hash value, the original key must be stored in the hash table. In this manner, the stored original key can be compared to the input to ensure a true match. For instance, there are as many as 212 or 4096 32-bit keys which could hash to the same key. To resolve any conflicts between “A” and “B”, the original “A” key is stored in hash table 401. Thereby, a simple comparison will resolve the conflict.
Applying hashing techniques to RAM memory has been very powerful and efficient. However, it would be even better, more efficient, and less expensive if one could somehow store even less data in the hash tables without reducing its efficacy. The present invention provides one such novel, unique solution. The present invention enables one to store less data in the hash table(s) without degrading any functionality whatsoever.